// 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。

#include<bits/stdc++.h>
using namespace std;

// 看了题解，类似于84，只不过把每一行看做一个84

// 执行用时：
// 76 ms
// , 在所有 C++ 提交中击败了
// 13.32%
// 的用户
// 内存消耗：
// 11.6 MB
// , 在所有 C++ 提交中击败了
// 55.20%
// 的用户

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        int res =0;
        if(matrix.empty()){
            return res;
        }
        int hang = matrix.size();
        int lie = matrix[0].size();
        vector<int> line(lie+2,0);
        for(int i=0;i<hang;i++){
            for(int j=0;j<lie;j++){
                if(matrix[i][j]=='1'){
                    line[j+1] = line[j+1]+1;
                }
                else{
                    line[j+1] = 0;
                }
            }
            res = max(res,upStack(line));
        }
        return res;
    }

    int upStack(vector<int>& line){
        int res = 0;
        stack<int> sta;
        sta.push(0);
        for(int i=1;i<line.size();i++){
            if(line[i]>=line[sta.top()]){
                sta.push(i);
            }
            else{
                while(!sta.empty()&&line[sta.top()]>line[i]){
                    int mid = sta.top();
                    sta.pop();
                    int left = sta.top();
                    int right = i;
                    int w = right - left - 1;
                    int h = line[mid];
                    res = max(res,w*h);
                    cout<<res<<endl;
                }
                sta.push(i);
            }
        }
        return res;
    }
};